Computers are binary systems which represent information using signals that can take on only two discrete values, 0 and 1. Each digit of a binary number is a bit having one of the two discrete values. Consequently, computers perform arithmetic computations such as addition, subtraction, multiplication and division in base two. To simplify the arithmetic operations, computers can represent binary numbers in several well-known formats, such as two's complement and signed-magnitude.
The magnitude of a number is determined by adding the positional value of each digit in the number. The positional value of a digit depends upon the position of that digit in the base notation of the number. The positional value of each digit in the notation increases by a power of the base from the preceding digit position to the next digit position. For example in radix-2, the magnitude of the four-bit binary number b.sub.3 b.sub.2 b.sub.1 b.sub.0 is: b.sub.3 .times.2.sup.3 +b.sub.2 .times.2.sup.2 +b.sub.1 .times.2.sup.1 +b.sub.0 .times.2.sup.0.
Conceptually, computers perform division in base two similarly to the traditional base ten long division techniques taught in elementary school. Algorithms used by computers to perform division fall into two broad categories: restoring and non-restoring, see Hennessy and Patterson, Computer Architecture A Quantitative Approach, 2nd Edition, Morgan Kaufmann Publishers, Inc. 1996, describe ordinary restoring and non-restoring algorithms at pages A-3 to A-7. A restoring algorithm restores negative partial remainders by adding the divisor to the partial remainder before performing the next division iteration. The traditional elementary school long division technique is an example of a restoring algorithm. In contrast, non-restoring algorithms skip the restoring step and carry negative partial remainders into the next division iteration.